/*
 * @Author: zxc
 * @Date: 2020-08-15 20:13:57
 * @LastEditTime: 2020-08-15 21:24:40
 * @LastEditors: zxc
 * @Description: 基数排序
 */
import { findMaxValue, findMinValue } from "../utils";

export function radixSort(array, radixBase = 10) {
  if (array.length < 2) {
    return array;
  }
  const minValue = findMinValue(array);
  const maxValue = findMaxValue(array);
  let significantDigit = 1;
  while ((maxValue - minValue) / significantDigit >= 1) {
    array = countingSortForRadix(array, radixBase, significantDigit, minValue);
    significantDigit *= radixBase;
  }
  return array;
}

const countingSortForRadix = (array, radixBase, significantDigit, minValue) => {
  let bucketsIndex;
  const buckets = [];
  const aux = [];
  for (let i = 0; i < radixBase; i++) {
    buckets[i] = 0;
  }
  // console.log(buckets)
  for (let i = 0; i < array.length; i++) {
    bucketsIndex = getBucketIndex(
      array[i],
      minValue,
      significantDigit,
      radixBase
    );
    buckets[bucketsIndex]++;
  }
  // console.log(buckets)

  /**
   * 在填充之前，我们需要得到每一个数在临时数组中准确的下标。
   * 于是我们可以使用buckets[i] += buckets[i-1]的方式获得某一位在临时数组中最右边的下标。
   * 什么意思呢？就是现在的buckets的值为{0,0,1,0,1,1,4,1,2,0}，
   * 所以个位为2的数应该在临时数组的第0位，个位为4的数应该在临时数组的第2位，
   * 个位为6的有4个，那么这四个数应该分别在临时数组的第3、4、5、6位上，
   * 在执行完buckets[i] += buckets[i-1]操作后就能获得每一位的最后一个在临时数组中最右边的位置了。
   */
  for (let i = 1; i < radixBase; i++) {
    // console.log(i+ " -- >" +buckets[i] + "-----" + buckets[i-1])
    buckets[i] += buckets[i - 1];
  }
  for (let i = array.length - 1; i >= 0; i--) {
    bucketsIndex = getBucketIndex(
      array[i],
      minValue,
      significantDigit,
      radixBase
    );
    aux[--buckets[bucketsIndex]] = array[i];
  }
  // console.log(aux)
  for (let i = 0; i < array.length; i++) {
    array[i] = aux[i];
  }
  return array;
};

const getBucketIndex = (value, minValue, significantDigit, radixBase) =>
  Math.floor(((value - minValue) / significantDigit) % radixBase);

let arr = [456, 789, 123, 1, 32, 4, 243, 321, 42, 90, 10, 999];
console.log(radixSort(arr));
